package 链表;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * 876. 链表的中间结点 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * <p>
 * User: zhaixiaolong Date:2024/1/4 14:54 ProjectName: algorithm Version:
 */
public class 两个链表的第一个公共节点 {

    public static List<Node> initData1() {

        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;

        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 6;
        Node node7 = new Node();
        node7.value = 7;
        Node node8 = new Node();
        node8.value = 8;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node6.next = node7;
        node7.next = node8;
        node8.next = node3;
        List<Node> list = new ArrayList<>();
        list.add(node1);
        list.add(node6);
        return list;
    }


    /**
     * 栈
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node intersect(Node head1, Node head2) {
        Stack<Node> stack1 = new Stack<>();
        Stack<Node> stack2 = new Stack<>();
        while (head1 != null) {
            stack1.push(head1);
            head1 = head1.next;
        }
        while (head2 != null) {
            stack2.push(head2);
            head2 = head2.next;
        }
        Node res = null;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            Node s1 = stack1.pop();
            Node s2 = stack2.pop();
            if (s1.value == s2.value) {
                res = s1;
            } else {
                return res;
            }
        }
        return res;
    }

    /**
     * a+b+c=c+b+a
     *
     * @param head1
     * @param head2
     * @return
     */
    public static Node intersect2(Node head1, Node head2) {

        Node index1 = head1;
        Node index2 = head2;
        while (index1 != null && index2 != null) {
            if (index1.value == index2.value) {
                return index1;
            }
            index1 = index1.next;
            index2 = index2.next;
            if (index1 == null && index2 != null) {
                index1 = head2;
            }
            if (index2 == null && index1 != null) {
                index2 = head1;
            }
        }
        return null;

    }

    public static void main(String[] args) {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;

        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 6;

        Node node7 = new Node();
        node7.value = 7;
        Node node8 = new Node();
        node8.value = 8;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node7;
        node7.next = node8;

        node5.next = node6;
        node6.next = node7;

        Node node = intersect2(node1, node5);
        System.out.println(node.value);

    }
}
